package main

import (
	"fmt"
)

// 逆向双指针
func merge88(nums1 []int, m int, nums2 []int, n int) {
	//定义i，j指针
	var i, j int = m - 1, n - 1
	var index int = m + n - 1
	for index > -1 {
		if i == -1 {
			//从nums2复制到nums1
			nums1[index] = nums2[j]
			j--
		} else if j == -1 {
			//nums1 不变
		} else if nums1[i] < nums2[j] {
			nums1[index] = nums2[j]
			j--
		} else {
			nums1[index] = nums1[i]
			i--
		}
		index--
	}
	fmt.Print(nums1)
}

func removeElement27(nums []int, val int) int {
	l, r := 0, 0
	for r < len(nums) {
		if nums[r] != val {
			nums[l] = nums[r]
			l++
		}
		r++
	}
	return l
}

func removeDuplicates26(nums []int) int {
	l, r := 0, 0
	for r < len(nums) {
		if nums[l] == nums[r] {
			nums[l] = nums[r]
		} else {
			l++
			nums[l] = nums[r]
		}
		r++
	}
	return l + 1
}

func removeDuplicates80(nums []int) int {
	count := 1
	index, r := 0, 1
	for r < len(nums) {
		if nums[index] == nums[r] {
			if count < 2 {
				count++
				index++
				nums[index] = nums[r]
			}
		} else {
			index++
			nums[index] = nums[r]
			count = 1
		}
		r++
	}
	return index + 1

}

func majorityElement169(nums []int) int {
	candidate := 0
	count := 0
	for _, v := range nums {
		if count == 0 {
			candidate = v
		}
		if candidate == v {
			count++
		} else {
			count--
		}
	}
	return candidate
}

func rotate189(nums []int, k int) {
	temp := make([]int, len(nums))
	length := len(nums)
	for i, v := range nums {
		temp[(i+k+length)%length] = v
	}
	copy(nums, temp)
}

// todo
func rotate189v2(nums []int, k int) {
	////使用临时变量，达到O(1)空间复杂度
	//length := len(nums)
	//pre := (length - k) % length
	//now := 0
	//var temp int
	//for now != pre {
	//	temp = nums[now]
	//
	//}
}

// 翻转方法
func rotate1892v3(nums []int, k int) {

	//1.初次翻转
	length := len(nums)
	k = k % length
	for i := 0; i < length/2; i++ {
		temp := nums[i]
		nums[i] = nums[length-1-i]
		nums[length-1-i] = temp
	}
	//2.二次翻转。根据k分割
	l := k / 2
	r := k + (length-k)/2 - 1
	for i := 0; i < length; i++ {
		if i < l {
			//左边翻转
			temp := nums[i]
			nums[i] = nums[k-1-i]
			nums[k-1-i] = temp
		}
		if i > r {
			//右边翻转
			temp := nums[i]
			nums[i] = nums[length-1-(i-k)]
			nums[length-1-(i-k)] = temp
		}
	}
}

func canWinNim292(n int) bool {
	//if n <= 3 {
	//	return true
	//} else if n <= 4 {
	//	return false
	//} else {
	//	return !(canWinNim292(n-1) && canWinNim292(n-2) && canWinNim292(n-3))
	//}
	return n%4 != 0
}

// 双端队列
func maxResult1696(nums []int, k int) int {
	length := len(nums)
	dp := make([]int, length)
	dp[0] = nums[0]
	deque := []int{0}
	for i := 1; i < length; i++ {
		//1.出列
		if deque[0] < i-k {
			deque = deque[1:]
		}
		//2.最大值
		dp[i] = dp[deque[0]] + nums[i]
		//3.维护优先队列
		for len(deque) > 0 && dp[i] >= dp[deque[len(deque)-1]] {
			deque = deque[:len(deque)-1]
		}
		//4.放入优先队列
		deque = append(deque, i)
	}
	return dp[length-1]
}

func maxProfit121(prices []int) int {
	if len(prices) == 1 {
		return 0
	}
	var p = []int{prices[0], prices[1]}
	res := p[1] - p[0]
	for i := 1; i < len(prices); i++ {
		if prices[i] <= p[0] {
			p[0] = prices[i]
			p[1] = 0
		}
		if prices[i] > p[1] {
			p[1] = prices[i]
			num := p[1] - p[0]
			if num > res {
				res = num
			}
		}
	}
	return res
}

func canJump(nums []int) bool {
	maxIndex := 0
	for i := 0; i < len(nums); i++ {
		if i <= maxIndex {
			current := nums[i] + i
			if current > maxIndex {
				maxIndex = current
			}
		}
	}
	return maxIndex >= len(nums)-1
}

/**
* 接雨水，动态规划
 */
func trap1(height []int) int {
	l := len(height)
	//左右数组，累计最大值
	left := make([]int, l)
	lmax := height[0]
	for index, value := range height {
		if value > lmax {
			lmax = value
		}
		left[index] = lmax
	}
	right := make([]int, l)
	rmax := height[l-1]
	for i := l - 1; i >= 0; i-- {
		if height[i] > rmax {
			rmax = height[i]
		}
		right[i] = rmax
	}
	var count int = 0
	for i := 0; i < l; i++ {
		if left[i] > right[i] {
			count += right[i] - height[i]
		} else {
			count += left[i] - height[i]
		}
	}
	return count
}

// 接雨水，双指针
func trap2(height []int) int {
	left, right := 0, len(height)-1
	lmax, rmax := 0, 0
	count := 0
	for left < right {
		lmax = max(lmax, height[left])
		rmax = max(rmax, height[right])
		if lmax < rmax {
			count += lmax - height[left]
			left++
		} else {
			count += rmax - height[right]
			right--
		}
	}
	return count
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {

	rotate1892v3([]int{1}, 2)

}
